package day1115;

/**
 * @Author:galaxy_yan
 * @Date: 2022/11/17
 * @Time: 16:07
 * @Description
 */
public class HashBucket {
   private static class Node{
        int key;
        int value;
        Node next;

       public Node(int key, int value) {
           this.key = key;
           this.value = value;
       }
   }
    // 定义哈希桶
    private Node[] bucket;
    // 当前有效元素的个数
    private int size;
    // 定义负载因子
    private final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashBucket () {
        bucket = new Node[8];
    }
    public int put(int key,int value){
//        找到应存放的位置
        int index=key%bucket.length;
        Node current=bucket[index];
        while (current!=null){
            if(current.key==key){
                current.value=value;
            }
            current=current.next;
        }
        Node node=new Node(key,value);
        node.next=bucket[index];
        bucket[index]=node;
        size++;
        if (loadFactor() >= DEFAULT_LOAD_FACTOR) {
//            扩容
            resize();
        }

        return 0;
    }

    // 扩容
    private void resize() {
//        1、按二倍的大小扩容
        Node[] array=new Node[bucket.length*2];
//        2、遍历数组，重新hash
        for (int i = 0; i < bucket.length; i++) {
            Node current=bucket[i];
            while (current!=null){
//                2.1记录下下一个节点
                Node next=current.next;
//                2.2 重新hash
                int index=current.key%array.length;
                current.next=array[index];
                array[index]=current;
//                2.3 继续向下移动，处理后续节点
                current=next;
        }
//            3、更新数组
            bucket=array;
        }
    }
    private float loadFactor(){
        return size*1.0f/ bucket.length;
    }
    private int get(int key){
//        1.找到key对应的index
        int index=key%bucket.length;
//        2.遍历index下的链表
        Node current=bucket[index];
        while(current!=null){
//            2.1如果找到直接返回
            if(current.key==key){
                return current.value;
            }
//            2.2一直遍历
            current=current.next;
        }
//        3.找不到返回-1
        return -1;
    }
}
